package 中等.前缀和与差分;

import java.util.Arrays;

/**
 * 给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 0 开始的字符串 s ，它只包含字符 '*'
 * 和 '|' ，其中 '*' 表示一个 盘子 ，'|' 表示一支 蜡烛 。
 * 同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [lefti, ii] 
 * 表示 子字符串 s[lefti...ii] （包含左右端点的字符）。对于每个查询，你需要找到 子字
 * 符串中 在 两支蜡烛之间 的盘子的 数目 。如果一个盘子在 子字符串中 左边和右边 都 至少有
 * 一支蜡烛，那么这个盘子满足在 两支蜡烛之间 。
 * 比方说，s = "||**||**|*" ，查询 [3, 8] ，表示的是子字符串 "*||**|" 。子字符串中在两支蜡
 * 烛之间的盘子数目为 2 ，子字符串中右边两个盘子在它们左边和右边 都 至少有一支蜡烛。
 * 请你返回一个整数数组 answer ，其中 answer[i] 是第 i 个查询的答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/plates-between-candles
 */
public class 蜡烛之间的盘子_2055 {

    public static void main(String[] args) {

        String str = "|******************************************************************************************************************************************************************|**********************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|******************************************************|***********************************************************************************************************************************************|**************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|****************************************************************************************************************************************************************************************************************|******************************************************************************************************************|**********************************************************************************************************************************************************************************************************************************************************************************************************************************|*******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|*************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|************************************************|*************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|**************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|***************************************************************************************************************************************************************************************************************************************************************************|***********************************************************************|***************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|*******************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|*************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************|****************************************************************************************************************************************************************|*";
        int[][] queries = {{2, 33}, {2, 32}, {3, 31}, {0, 33}};
        System.out.println(Arrays.toString(new 蜡烛之间的盘子_2055().efficientPlatesBetweenCandles(str, queries)));

    }

    public int[] platesBetweenCandles(String s, int[][] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = getQuery(s, queries[i]);
        }
        return ans;
    }

    public int getQuery(String s, int[] query) {
        int left = query[0];
        int i = query[1];
        int curAns = 0;
        while (i > left && s.charAt(i) != '|') {
            i--;
        }
        while (left < i && s.charAt(left) != '|') {
            left++;
        }
        for (int cur = left + 1; cur < i; cur++) {
            if (s.charAt(cur) == '*') {
                curAns++;
            }
        }
        return curAns;
    }

    /**
     * 预处理+动态规划+二分查找+前缀和
     * 用一个dp[i]来表示字符串中0~i的满足条件的盘子数目是多少
     * 用一个数组来存储蜡烛出现的索引位置
     *
     * @param s
     * @param queries
     * @return
     */
    public int[] efficientPlatesBetweenCandles(String s, int[][] queries) {
        int[] ans = new int[queries.length];
        int[] dp = new int[s.length()];
        int[] candles = new int[s.length()];  //用来保存蜡烛所在的索引，递增
        int candleIndex = 0;
        if (s.charAt(0) == '|') {
            candleIndex++;
        }
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '*') {  //如果当前不是蜡烛，那么满足条件的最多盘子数目和0~i-1的子串相同
                dp[i] = dp[i - 1];
            } else {
                int left = i - 1;
                if (candleIndex > 0) { //这里无需二分查找，找到左边的第一根蜡烛
                    left = candles[candleIndex - 1];
                }
                if (left >= 0) { //左边的第一根蜡烛总数，加上新增的的盘子
                    dp[i] = dp[left] + i - left - 1;
                }
                candles[candleIndex] = i;  //保存蜡烛
                candleIndex++;
            }
        }
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            if (s.charAt(left) != '|') {  //如果左边界不是蜡烛，则需要找到大于左边界的第一根蜡烛
                left = getAfterCandle(candles, left, candleIndex);
            }
            if (left > right) continue;
            ans[i] = dp[right] - dp[left];
        }
        return ans;
    }

    /**
     * 需要找到比target大与等于的第一个数
     *
     * @param candles
     * @param target
     * @return
     */
    public int getAfterCandle(int[] candles, int target, int right) {
        int left = 0, ans = candles.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cur = candles[mid];
            if (cur == target) {
                return cur;
            } else if (cur > target) {
                ans = cur;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
